package demo.practice.competition;

import java.util.HashSet;
import java.util.Set;

public class P5793 {

    public static void main(String[] args) {
        P5793 p5793 = new P5793();
        int i = p5793.nearestExit(new char[][]{{'.', '.'}}, new int[]{0, 1});
        System.out.println(i);
    }

    public int nearestExit(char[][] maze, int[] entrance) {
        int i = entrance[0], j = entrance[1];

        int go = go(maze, i, j, new HashSet<>(), i, j);
        return go < 2 ? -1 : go - 1;
    }

    private int go(char[][] maze, int i, int j, Set<String> set, int oi, int oj) {


        if (i >= maze.length || i < 0)
            return 0;

        if (j > maze[i].length || j < 0)
            return 0;

        if (maze[i][j] == '+' || set.contains(i + "_" + j)) {
            return -1;
        }

        Set<String> cs = new HashSet<String>(set);
        cs.add(i + "_" + j);

        int ch1 = go(maze, i + 1, j, cs, oi, oj);
        int ch2 = go(maze, i - 1, j, cs, oi, oj);
        int ch3 = go(maze, i, j + 1, cs, oi, oj);
        int ch4 = go(maze, i, j - 1, cs, oi, oj);

        if (ch1 == -1 && ch2 == -1 && ch3 == -1 && ch4 == -1)
            return -1;


        int add = Integer.MAX_VALUE;
        if (ch1 != -1 && !(ch1 == 0 && i == oi && j == oj))
            add = Math.min(add, ch1);

        if (ch2 != -1 && !(ch2 == 0 && i == oi && j == oj))
            add = Math.min(add, ch2);

        if (ch3 != -1 && !(ch3 == 0 && i == oi && j == oj))
            add = Math.min(add, ch3);

        if (ch4 != -1 && !(ch4 == 0 && i == oi && j == oj))
            add = Math.min(add, ch4);

        return 1 + add;
    }

}
